package com.leetcode.offer.chapter2;

/**
 * @author Dennis Li
 * @date 2020/7/11 21:55
 */
public class FrogNumWays_10_2 {

    public static void main(String[] args) {
        System.out.println(new FrogNumWays_10_2().numWays(100));
    }

    // 重点在于问题的转换 -- 如何将跳台类比称为斐波那契数列
    public int numWays(int n) {
        // 这里有点搞,0级台阶也要跳，没想到的
        if (n <= 1) return 1;
        // 避免大数相加，用long
        long[] result = {1, 1};
        long temp = 0;
        for (int i = 2; i <= n; i++) {
            temp = (result[0] + result[1]) % 1000000007;
            result[0] = result[1];
            result[1] = temp;
        }
        // 取模再转换成int
        return (int)(temp % 1000000007);
    }

}
